package LinkedList;
//两两交换链表中的节点

public class swap_nodes_in_pairs {

    static class ListNode{
        int val;
        ListNode next;
        public ListNode(int val){
            this.val=val;
        }
    }
    //给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。
    // 你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
    public static ListNode swapPairs(ListNode head) {
        //这里注意先去判断
        if(head==null||head.next==null){
            return head;
        }
        //这里先去交换
        //这里先去记录头节点dummy
        ListNode dummy=new ListNode(0);
        dummy.next=head;
        //定义当前节点的pre节点 方便去交换
        ListNode pre=dummy;
        //现在是 dummy(pre)-->head-->head.next
        // dummy-->1-->2-->3
        ListNode right=head.next; //2
        ListNode left=head; //1
        while (left!=null&&left.next!=null){
//            swap(pre,head,head.next);
            //记录原来的顺序
            ListNode oldNext=right.next;//3
            //翻转
            pre.next=right;
            right.next=left;
            left.next=oldNext;
            //将每一个都走进下一步 方便下一次循环
            pre=pre.next.next;
            left=left.next;
            if(left.next==null){
                break;
            }else {
                right=left.next;
            }

        }
        return dummy.next;
    }

    public static void main(String[] args) {
        ListNode head=new ListNode(1);
        ListNode head2=new ListNode(2);
        ListNode head3=new ListNode(3);
        ListNode head4=new ListNode(4);
        head.next=head2;
        head2.next=head3;
        head3.next=head4;
        swapPairs(head);
    }
//    public ListNode swap(ListNode pre,ListNode left,ListNode right){
//
//    }
}
